//
// Created by Administrator on 2021/5/26.
//

//从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        queue<TreeNode *> q;
        vector<vector<int>> ans;
        if (root==nullptr) return ans;
        q.push(root);
        while (!q.empty()) {
            int n = (int) q.size();
            vector<int> level;
            for (int i = 0; i < n; ++i) {
                auto f = q.front();
                q.pop();
                level.push_back(f->val);
                if (f->left) q.push(f->left);
                if (f->right) q.push(f->right);
            }
            ans.push_back(level);
        }
        return ans;
    }
};

int main() {
//    [3,9,20,null,null,15,7]
    auto t5 = TreeNode(7), t4 = TreeNode(15), t3 = TreeNode(20), t2 = TreeNode(9), t1 = TreeNode(3);
    t1.left = &t2;
    t1.right = &t3;
    t3.left = &t4;
    t3.right = &t5;
    auto sol = Solution();
    vector<vector<int>> ans = sol.levelOrder(&t1);
    for (auto &an : ans) {
        for (int j : an) {
            cout << j << endl;
        }
        cout << "----" << endl;
    }
    return 0;
}
